package com.cuz.for2024;

public class T639 {
    public static void main(String[] args) {
        System.out.println(new T639().numDecodings("1*"));
        System.out.println(new T639().numDecodings("3*"));
    }

    public int numDecodings(String s) {
        return numDecodings3(s);
    }

    static final int MOD = 1000000007;

    public int numDecodings2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] charArray = s.toCharArray();
        if (charArray[0] == '0') {
            return 0;
        }
        int[] dp = new int[charArray.length];
        dp[charArray.length - 1] = count(charArray[charArray.length - 1]);
        for (int index = charArray.length - 2; index >= 0; index--) {
            char nowChar = charArray[index];
            if (nowChar == '0') {
                dp[index] = 0;
                continue;
            }
            dp[index] = dp[index + 1];
            if (index + 1 < charArray.length) {
                if ((charArray[index + 1] - '0') + (nowChar - '0') * 10 <= 26) {
                    dp[index] += index + 2 >= dp.length ? 1 : dp[index + 2];
                }
            }
        }
        return dp[0];
    }

    public int numDecodings3(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        if (s.length() == 1) {
            return count(s.charAt(0));
        }
        if (s.length() == 2) {
            if (s.charAt(0) != '*' || s.charAt(0) > '2') {
                return count(s.charAt(1));
            }
            return count(s.charAt(0)) * count(s.charAt(1)) + count(s.charAt(0), s.charAt(1));
        }
        char[] charArray = s.toCharArray();
        if (charArray[0] == '0') {
            return 0;
        }
        // dp[i] 0~i 的组合数
        // dp[i] = 自己*dp[i-1]
        // +  自己和前面组合 * dp[i-2]
        // dp[i-1]
        long pre = count(charArray[0]);
        //dp[i-2]
        long prePre = charArray[0] <= '2' ? 1 : 0;
        // *1 2
        for (int i = 1; i < charArray.length; i++) {
            long now = (count(charArray[i]) * pre) % MOD;
            now += (count(charArray[i - 1], charArray[i]) * prePre) % MOD;

            prePre = pre;
            pre = now;
        }
        return (int) pre;
    }

    private int count(char pre) {
        if (pre == '0') {
            return 0;
        }
        return pre == '*' ? 9 : 1;
    }

    private int count(char pre, char next) {
        if (pre == '0') {
            return 0;
        }
        if (pre == '*' && next == '*') {
            return 15;
        }
        if (pre == '*') {
            return next <= '6' ? 2 : 1;
        }
        if (next == '*') {
            return pre == '1' ? 9 : 6;
        }
        return (pre - '0') * 10 + (next - '0') <= 26 ? 1 : 0;
    }


}
